package com.lb.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 状态压缩＋哈希表。类似的题出现好几次了。 如1124。 状态压缩后，哈希表的用处是求最长的连续子串，满足子数组的和为k。 此题k为0， 1124题k为1.
 *
 * 遇到奇偶个数校验，想到XOR
 * 遇到有限的参数（小于20个）表状态， 想到状态压缩 （bitmask）
 * 遇到求最长的连续子串使得和为k（maximum continuous subarray(substring) with sum equal to k）想到 前缀和 加哈希表记录第一次出现某一状态的位置。
 */
public class Solution {
    
    private static final String VOWELS = "aeiou";

    public int findTheLongestSubstring(String s) {
        Map<Integer, Integer> map = new HashMap<>();
        int size = s.length();
        int state = 0; // (00000)
        int maxSize = 0;
        map.putIfAbsent(0, -1);
        for (int i = 0; i < size; i ++){
            for (int k = 0; k < VOWELS.length(); k++){
                if (s.charAt(i) == VOWELS.charAt(k)){
                    state ^= (1 << (VOWELS.length() - k - 1));
                    break; 
                }
            }
            if (map.containsKey(state)){
                maxSize = Math.max(maxSize, i - map.get(state));
            }
            map.putIfAbsent(state, i);
        }

        return maxSize;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findTheLongestSubstring("koood"));
    }
}